package main

// 189. 轮转数组
func main() {
	//nums, k := []int{1, 2, 3, 4, 5, 6, 7}, 3
	nums, k := []int{-1, -100, 3, 99}, 2
	//nums, k := []int{1, 2, 3}, 3
	rotateArray2(nums, k)

	for _, n := range nums {
		print(n, " ")
	}
}

func rotateArray2(nums []int, k int) {
	// 解法2， 反转数组
	// 该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 k % n 个元素会移动至数组头部，其余元素向后移动 k % n个位置。
	// 该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 k % n 个元素就被移至数组头部，然后我们再翻转 [0,k % n−1] 区间的元素和 [k % n,n−1] 区间的元素即能得到最后的答案。
	k %= len(nums)
	reverseArray(nums, 0, len(nums)-1)
	reverseArray(nums, 0, k-1)
	reverseArray(nums, k, len(nums)-1)

	return
}

func reverseArray(nums []int, start, end int) {
	if start > len(nums)-1 || start < 0 || end > len(nums)-1 || end < 0 {
		return
	}
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
	return
}

func rotateArray(nums []int, k int) {
	// 解法1， 找到每个点未来的位置
	var originNums []int
	for _, n := range nums {
		originNums = append(originNums, n)
	}

	for i := 0; i < len(nums); i++ {
		newIdx := (i + k) % len(nums)
		nums[newIdx] = originNums[i]
	}

	return
}

// class Solution {
//  public void rotate(int[] nums, int k) {
//    k %= nums.length;
//    reverse(nums, 0, nums.length - 1);
//    reverse(nums, 0, k - 1);
//    reverse(nums, k, nums.length - 1);
//  }
//
//  public void reverse(int[] nums, int start, int end) {
//    while (start < end) {
//      int temp = nums[start];
//      nums[start] = nums[end];
//      nums[end] = temp;
//      start += 1;
//      end -= 1;
//    }
//  }
//}

//给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
//
//示例 1:
//
//输入: nums = [1,2,3,4,5,6,7], k = 3
//输出: [5,6,7,1,2,3,4]
//解释:
//向右轮转 1 步: [7,1,2,3,4,5,6]
//向右轮转 2 步: [6,7,1,2,3,4,5]
//向右轮转 3 步: [5,6,7,1,2,3,4]
//示例 2:
//
//输入：nums = [-1,-100,3,99], k = 2
//输出：[3,99,-1,-100]
//解释:
//向右轮转 1 步: [99,-1,-100,3]
//向右轮转 2 步: [3,99,-1,-100]
//
//
//提示：
//
//1 <= nums.length <= 105
//-231 <= nums[i] <= 231 - 1
//0 <= k <= 105
